class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> results;

        if(intervals.size() == 0)
        {
            results.emplace_back(newInterval);
            return results;
        }

        int mergeBegin = 0;
        int mergeEnd = 0;

        for(int i = 0; i < intervals.size(); ++i)
        {
            if(newInterval[0] >= intervals[i][0] && newInterval[0] <= intervals[i][1])
            {
                mergeBegin = i;
            }
            if(newInterval[1] >= intervals[i][0] && newInterval[1] <= intervals[i][1])
            {
                mergeEnd = i;
            }
        }

        cout << "mergeBegin: " << mergeBegin << " " << "mergeEnd: " << mergeEnd << endl; 

        bool flag = true;
        for(int i = 0; i < intervals.size(); ++i)
        {
            if(i < mergeBegin || i > mergeEnd)
            {
                results.emplace_back(intervals[i]);
            }
            else
            {
                if(flag)
                {
                    int leftNum = intervals[mergeBegin][0];
                    int rightNum = max(intervals[mergeEnd][1], newInterval[1]);
                    vector<int> temp({leftNum, rightNum});
                    results.emplace_back(temp);
                    flag = false;
                }
            }
        }

        return results;
    }
};

// [1,2],[3,5],[6,7],[8,10],[12,16]
//        [4,         8]

